#include <stdio.h>
#include <stdlib.h>

#define ElementType int
#define ERROR 1e5
typedef enum { push, pop, inject, eject, end } Operation;

typedef struct Node *PtrToNode;
struct Node {
    ElementType Element;
    PtrToNode Next, Last;
};
typedef struct DequeRecord *Deque;
struct DequeRecord {
    PtrToNode Front, Rear;
};
Deque CreateDeque();
int Push( ElementType X, Deque D );
ElementType Pop( Deque D );
int Inject( ElementType X, Deque D );
ElementType Eject( Deque D );

Operation GetOp();          /* details omitted */
void PrintDeque( Deque D ); /* details omitted */

int main()
{
    ElementType X;
    Deque D;
    int done = 0;
    
    D = CreateDeque();
    while (!done) {
        switch(GetOp()) {
            case push:
                scanf("%d", &X);
                if (!Push(X, D)) printf("Memory is Full!\n");
                break;
            case pop:
                X = Pop(D);
                if ( X==ERROR ) printf("Deque is Empty!\n");
                break;
            case inject:
                scanf("%d", &X);
                if (!Inject(X, D)) printf("Memory is Full!\n");
                break;
            case eject:
                X = Eject(D);
                if ( X==ERROR ) printf("Deque is Empty!\n");
                break;
            case end:
                PrintDeque(D);
                done = 1;
                break;
        }
    }
    return 0;
}

/* Your function will be put here */
/* Your function will be put here */
Deque CreateDeque()
{
    Deque ans=malloc(sizeof(struct DequeRecord));
    PtrToNode tmp=malloc(sizeof(struct Node));
    tmp->Next=NULL;
    tmp->Last=NULL;
    
    ans->Front=tmp;
    ans->Rear=tmp;
    return ans;
}
int Push( ElementType X, Deque D )
{
    PtrToNode tmp=malloc(sizeof(struct Node));
    tmp->Element=X;
    if(D->Front==D->Rear)
    {
        D->Front->Next=tmp;
        tmp->Last=D->Front;
        D->Rear=tmp;
        tmp->Next=NULL;
    }
    else
    {
        tmp->Next=D->Front->Next;
        tmp->Last=D->Front;
        D->Front->Next->Last=tmp;
        D->Front->Next=tmp;
    }
    return 1;
}
ElementType Pop( Deque D )
{
    if(D->Front==D->Rear)return ERROR;
    ElementType tmp=D->Front->Next->Element;
    PtrToNode   t  =D->Front->Next;
    if(D->Front->Next==D->Rear)
    {
        D->Rear=D->Front;
        D->Rear->Next = NULL;
    }
    else
    {
        D->Front->Next->Next->Last = D->Front;
        D->Front->Next = D->Front->Next->Next;
    }
    free(t);
    return tmp;
}
int Inject( ElementType X, Deque D )
{
    PtrToNode tmp=malloc(sizeof(struct Node));
    tmp->Element=X;
    if(D->Front==D->Rear)
    {
        D->Front->Next=tmp;
        tmp->Last=D->Front;
        D->Rear=tmp;
        tmp->Next=NULL;
    }
    else
    {
        D->Rear->Next=tmp;
        tmp->Last=D->Rear;
        tmp->Next=NULL;
        D->Rear=tmp;
    }
    return 1;
}
ElementType Eject( Deque D )
{
    if(D->Front==D->Rear)return ERROR;
    ElementType tmp=D->Rear->Element;
    PtrToNode   t  =D->Rear;
    D->Rear=D->Rear->Last;
    D->Rear->Next=NULL;
    free(t);
    return tmp;
}